An increasing number of applications today make use of digital video for various purposes including, for example, remote business meetings via video conferencing, high definition video entertainment, video advertisements, and sharing of user-generated videos. As technology is evolving, users have higher expectations for video quality and expect high resolution video even when transmitted over communications channels having limited bandwidth.
To permit higher quality transmission of video while limiting bandwidth consumption, a number of video compression schemes are noted including formats such as VPx, promulgated by Google, Inc. of Mountain View, Calif., and H.264, a standard promulgated by ITU-T Video Coding Experts Group (VCEG) and the ISO/IEC Moving Picture Experts Group (MPEG), including present and future versions thereof. H.264 is also known as MPEG-4 Part 10 or MPEG-4 AVC (formally, ISO/IEC 14496-10).
These compression schemes may use different techniques to achieve compression. For example, many of these schemes use prediction techniques that predict where information contained in a portion of a first frame or first region of a frame can be found in a second frame or second region of the frame. The difference between the prediction and the portion of data in the second frame or second frame region is calculated to form a residual. One type of prediction, known as intra prediction, can be based on previously coded image samples within the current frame. Another type of prediction known as inter prediction can be based on previously coded frames (“reference frames”). One inter prediction technique, for example, can utilize block-based motion estimation and compensation. Motion estimation can involve searching for a sample region in a reference frame that, for example, closely matches a current block in a current frame. The luma and chroma samples of the matching sample region are subtracted from the current block to produce a residual that is encoded. A motion vector is also encoded that describes the position of the matching sample region relative to the position of the current block.
In some motion estimation search algorithms, there is a trade-off between the computational efficiency of the algorithm and the quality of the prediction (i.e. finding the matching region). In other words, finding the “best” matching region may come with the cost of increased computations. Conversely, decreasing the computational complexity may result in not finding the most suitable matching region.